Search for: All records

Abstract—We study a problem of constructing codes that transform a channel with high bit error rate (BER) into one with low BER (at the expense of rate). Our focus is on obtaining codes with smooth (“graceful”) input-output BER curves (as opposed to threshold-like curves typical for long error-correcting codes). This paper restricts attention to binary erasure channels (BEC) and contains two contributions. First, we introduce the notion of Low Density Majority Codes (LDMCs). These codes are non-linear sparse-graph codes, which output majority function evaluated on randomly chosen small subsets of the data bits. This is similar to Low Density Generator Matrix codes (LDGMs), except that the XOR function is replaced with the majority. We show that even with a few iterations of belief propagation (BP) the attained input-output curves provably improve upon performance of any linear systematic code. The effect of nonlinearity bootstraping the initial iterations of BP, suggests that LDMCs should improve performance in various applications where LDGMs have been used traditionally. Second, we establish several two-point converse bounds that lower bound the BER achievable at one erasure probability as a function of BER achieved at another one. The novel nature of our bounds is that they are specific to subclasses of codes (linear systematic and non-linear systematic) and outperform similar bounds implied by the area theorem for the EXIT function 

—Consider a linear code defined as a mapping between vector spaces of dimensions k and n. Let β∗ denote the minimal (relative) weight among all images of input vectors of full Hamming weight k. Operationally, β∗ characterizes the threshold for adversarial (erasure) noise beyond which decoder is guaranteed to produce estimate of k-input with 100% symbol error rate (SER). This paper studies the relation between β∗ and δ, the minimum distance of the code, which gives the threshold for 0% SER. An optimal tradeoff between β∗ and δ is obtained (over large alphabets) and all linear codes achieving β∗ = 1 are classified: they are repetition-like. More generally, a design criteria is proposed for codes with favorable graceful degradation properties. As an example, it is shown that in an overdetermined system of n homogeneous linear equations in k variables (over a field) it is always possible to satisfy some k − 1 equations with non-zero assignments to every unknown, provided that any subset of k equations is linearly independent. This statement is true if and only if n ≥ 2k − 1. 

This paper introduces the notion of triangulation codes, a family of non-linear codes that 1) admit efficient encoding/decoding 2) their bit error rate deteriorates gracefully as the quality of the erasure channel degrades. Some coding theoretic properties of these codes are established. In the case of transmitting data over the erasure channel, it is shown that, even with sub-optimal decoding, they can achieve lower bit error rate than uncoded transmission for any number of received output symbols.